1. Field of the Invention
The present invention relates to generalized clipping in an extended frame buffer and, more particularly, to clipping by tracing the boundary of an object to be clipped and the boundary of the clipping region.
2. Description of the Related Art
Clipping is a common and useful operation in computer graphics. It can, for example, allow the computer to model a large and complex "world" of graphical objects, and present to the user only that portion which is of current interest. Clipping is the technique of displaying only the portion of an image which lies within some boundary. Those areas of the image which fall outside the boundary are said to be clipped away. There is a fair body of research into techniques for fast clipping, most of it oriented towards clipping to a rectangular boundary aligned with the coordinate axes. Also, some of the techniques are designed for clipping line segments (or vectors) rather than solid areas, such as polygons. However, there are methods which will clip polygon objects which can be generalized to clipping regions which are convex polygons.
Modern page description languages specify areas which can be bounded not only by line segments, but also by conic- or cubic-curve segments. These generalized polygons can be used to describe shapes to be filled with some color or regions for clipping. This generalized clipping problem has been handled by first approximating the curved segments in both the clipping region, and the region being clipped by a number of small line segments. The clipping region is then decomposed into convex areas (usually rectangles or trapezoids). Using these areas, known clipping techniques can be applied. Usually, the boundary segments of the object being clipped and the clipping regions are sorted (for example, into scanline order), so that it is easy to tell which segments might intersect which clipping areas, and the cost of checking all segments against all clipping regions can be avoided.
The related art has disclosed devices employing clipping to display only the portion of an image which lies within some boundary.
U.S. Pat. No. 4,698,779 to Holden et al discloses a graphic display with determination of coincidence of subject and clip area wherein a method to calculate an intersection between two lines using algebra is shown. A means is disclosed to detect an intersection between a subject region and a clip region.
U.S. Pat. No. 4,815,009 to Blatin discloses an algorithm for filling an image outline wherein a winding number is used to keep track of an outline of a polygon. An algorithm is provided which fills a polygon using a winding number system.
U.S. Pat. No. 3,816,726 to Southerland et al discloses a computer graphics clipping system for polygons which performs a clipping function in a three dimensional space. A line is clipped using several claims as references. A means is disclosed to calculate an intersection point between a plane and a polygon.
U.S. Pat. No. 4,623,880 to Bresenham et al discloses a graphics display system and method having an improved clipping technique which calculates an intersection between a clipping region and a subject region. An end point of a line is clipped if that end point is outside a view port. A system of vectors is used to define a clipping area.
U.S. Pat. No. 4,492,956 to Collmeyer et al discloses a graphics display system and method including a preclipping circuit wherein a hardware system is described for clipping. The system uses vector notation to keep track of lines and their intersections.
U.S. Pat. No. 4,906,986 to Takeda discloses a guard band clipping method for three dimensional graphics display systems wherein triangular polygons are used to represent a three dimensional space. In order to reduce the number of necessary clippings, a guard band is created around a clipping region. Before a polygon is clipped, it is sorted into one of four classes to determine if clipping is necessary. A method of determining whether or not a polygon should be clipped is shown.
U.S. Pat. No. 4,881,130 to Hayashi discloses an image editing system for an image recording apparatus wherein a particular region within a window is selected using a polygon. The polygon can be of any shape since a vector is used to define the polygon's boundary.
U.S. Pat. No. 4,888,712 to Barkans et al discloses a display control device wherein a frame buffer is used to store a boundary of an object. The frame buffer allows a user to fill in the background of a screen with a certain pattern which is repeated over and over again. Several methods of storing a pattern shown.
It would be desirable to perform a generalized clipping operation in a quick and efficient manner. It would further be desirable to perform the generalized clipping on a plurality of boundary shapes. These aspects are not addressed in the patents discussed above.